#!/usr/bin/python3
import sys
import re

# part 1

def get_bounds(tiles):
    min_x = sys.maxsize
    min_y = sys.maxsize
    max_x = 0
    max_y = 0
    for x in tiles:
        for y in tiles[x]:
            if x < min_x: min_x = x
            if x > max_x: max_x = x
            if y < min_y: min_y = y
            if y > max_y: max_y = y
    return (min_x, min_y, max_x, max_y)

def print_grid(tiles, bounds):
    min_x, min_y, max_x, max_y = bounds
    for y in range(min_y, max_y + 1):
        for x in range(min_x, max_x + 1):
            if x in tiles and y in tiles[x]:
                print(tiles[x][y], end='')
            else:
                print(' ', end='')
        print()

def try_add(tiles, x, y, tile):
    if x not in tiles:
        tiles[x] = {y: tile}
    else:
        tiles[x][y] = tile

def part1():
    tiles = {}
    coverage = {}
    target = 2000000
    for line in sys.stdin:
        sx, sy, bx, by = [int(g) for g in re.match(r'Sensor at x=(-?[0-9]+), y=(-?[0-9]+): closest beacon is at x=(-?[0-9]+), y=(-?[0-9]+)', line.strip()).groups()]

        try_add(tiles, sx, sy, 'S')
        try_add(tiles, bx, by, 'B')

        dist = abs(sx - bx) + abs(sy - by)
        print('distloop for', sx, sy, bx, by, dist)
        for y in range(sy - dist, sy + dist + 1):
            if y != target:
                continue
            for x in range(sx - dist + abs(y - sy), sx + dist + 1 - abs(y - sy)):
                if not (x in tiles and y in tiles[x]):
                    try_add(coverage, x, y, '#')
    min_x, min_y, max_x, max_y = get_bounds(coverage)
    print(min_x, min_y, max_x, max_y)
    countable = 0
    for x in range(min_x, max_x + 1):
        if x in coverage and target in coverage[x]:
            countable += 1
    print(f'counted {countable} positions')

# part 2

def overlap(a, b):
    return (a[0] <= b[0] and a[1] >= b[0]) or (b[0] <= a[0] and b[1] >= a[0])

def merge_intervals(intervals):
    if len(intervals) <= 1:
        return intervals
    a = intervals[0]
    b = intervals[1]
    # wider gap is necessary for "overlap"
    if overlap(a, (b[0] - 1, b[1])):
        return merge_intervals([(min(a[0], b[0]), max(a[1], b[1]))] + intervals[2:])
    else:
        return [a] + merge_intervals(intervals[2:])

def part2():
    pairs = set()
    sensors = []
    beacons = []
    if False:
        bound = 20
    else:
        bound = 4000000

    for line in sys.stdin:
        sx, sy, bx, by = [int(g) for g in re.match(r'Sensor at x=(-?[0-9]+), y=(-?[0-9]+): closest beacon is at x=(-?[0-9]+), y=(-?[0-9]+)', line.strip()).groups()]
        pairs.add((sx, sy, bx, by))
        sensors.append((sx, sy))
        beacons.append((bx, by))
    print(pairs)

    for y in range(0, bound + 1):
        intervals = []
        for sx, sy, bx, by in pairs:
            dist = abs(sx - bx) + abs(sy - by)
            max_y_dist = abs(y - sy)
            if max_y_dist > dist:
                continue
            max_x_dist = dist - max_y_dist
            intervals.append((sx - max_x_dist, sx + max_x_dist))
        intervals.sort()
        merged = merge_intervals(intervals)
        #print(intervals, '->', merged)
        if len(merged) > 1:
            print('aaaa', merged)
            for a, b in zip(merged[:-1], merged[1:]):
                x = a[1] + 1
                print(f'found gap at ({x}, {y}) with frequency {x * 4000000 + y}')

if sys.argv[1] in '1':
    part1()
else:
    part2()